//Copyright (C) 2012  Lynx Fang<lynx.cpp@gmail.com>
//
//This program is a part of large-int.
//
//Large-int is free software: you can redistribute it and/or modify
//it under the terms of the GNU Lesser General Public License as published by
//the Free Software Foundation, either version 3 of the License, or
//(at your option) any later version.
//
//Large-int is distributed in the hope that it will be useful,
//but WITHOUT ANY WARRANTY; without even the implied warranty of
//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//GNU Lesser General Public License for more details.
//
//You should have received a copy of the GNU Lesser General Public License
//along with this program.  If not, see <http://www.gnu.org/licenses/>.
//

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <assert.h>
#include <vector>
//#define LARGE_ARY_EN
#ifdef LARGE_ARY_EN
    #define ARY 10000
#else
    #define ARY 10
#endif

using namespace std;

class large_int;

class basic_large_int
{
    friend class large_int;
    friend basic_large_int operator+(const basic_large_int &,const basic_large_int &);
    friend basic_large_int operator-(const basic_large_int &,const basic_large_int &);
    friend basic_large_int operator*(const basic_large_int &,const basic_large_int &);
    friend basic_large_int operator/(basic_large_int ,const basic_large_int &);
    friend basic_large_int operator%(basic_large_int ,const basic_large_int &);
    friend bool operator==(const basic_large_int &,const basic_large_int &);
    friend bool operator!=(const basic_large_int &,const basic_large_int &);
    friend bool operator<(const basic_large_int &,const basic_large_int &);
    friend bool operator>(const basic_large_int &,const basic_large_int &);
    friend bool operator<=(const basic_large_int &,const basic_large_int &);
    friend bool operator>=(const basic_large_int &,const basic_large_int &);
    vector<int> a;

    public:
    basic_large_int();
    basic_large_int(const int &x);

    basic_large_int(string s);
    int len() const;
    void minimize_length();
    string str() const;
    int operator[](const int &x) const;
    basic_large_int operator=(const int &x);
    basic_large_int operator+=(const basic_large_int &y);
    basic_large_int operator-=(const basic_large_int &y);
    basic_large_int operator/=(const basic_large_int &y);
    basic_large_int operator*=(const basic_large_int &y);
    basic_large_int operator%=(const basic_large_int &y);

    private:
    void carry();
};

istream& operator>>(istream &is,basic_large_int &x);
ostream& operator<<(ostream &os,const basic_large_int &x);
basic_large_int operator+(const basic_large_int &,const basic_large_int &);
basic_large_int operator-(const basic_large_int &,const basic_large_int &);
basic_large_int operator*(const basic_large_int &,const basic_large_int &);
basic_large_int operator/(basic_large_int ,const basic_large_int &);
basic_large_int operator%(basic_large_int ,const basic_large_int &);
bool operator==(const basic_large_int &,const basic_large_int &);
bool operator!=(const basic_large_int &,const basic_large_int &);
bool operator<(const basic_large_int &,const basic_large_int &);
bool operator>(const basic_large_int &,const basic_large_int &);
bool operator<=(const basic_large_int &,const basic_large_int &);
bool operator>=(const basic_large_int &,const basic_large_int &);


basic_large_int::basic_large_int() { a.resize(1); a[0] = 0; }
basic_large_int::basic_large_int(const int &x)
{
    a.resize(1);
    a[0] = x;
    carry();
}

void basic_large_int::minimize_length() { a.resize(len()); }
int basic_large_int::operator[](const int &x) const { return a[x]; }

int basic_large_int::len() const
{
    int ret = a.size() - 1;
    while (ret>0){
        if (a[ret]!=0)
            break;
        ret --;
    }
    return ret + 1;
}


bool operator!=(const basic_large_int &x,const basic_large_int &y) { return !(x==y); }

bool operator<=(const basic_large_int &x,const basic_large_int &y) { return !(x>y); }
bool operator>=(const basic_large_int &x,const basic_large_int &y) { return !(x<y); }

basic_large_int operator+(const basic_large_int &x,const basic_large_int &y)
{
    basic_large_int ans;
    ans = x;
    ans += y;
    return ans;
}

basic_large_int operator-(const basic_large_int &x,const basic_large_int &y)
{
    basic_large_int ans;
    ans = x;
    ans -= y;
    return ans;
}

basic_large_int basic_large_int::operator*=(const basic_large_int &y) { return (*this) = (*this)*y; }
basic_large_int basic_large_int::operator/=(const basic_large_int &y) { return (*this) = (*this)/y; }
basic_large_int basic_large_int::operator%=(const basic_large_int &y) { return (*this) = (*this)%y; }


class large_int
{
    friend large_int operator+(const large_int &x,const large_int &y);
    friend large_int operator-(const large_int &x,const large_int &y);
    friend large_int operator*(const large_int &x,const large_int &y);
    friend large_int operator/(const large_int &x,const large_int &y);
    friend large_int operator%(const large_int &,const large_int &);
    friend bool operator==(const large_int &x,const large_int &y);
    friend bool operator>=(const large_int &x,const large_int &y);
    friend bool operator<=(const large_int &x,const large_int &y);
    friend bool operator>(const large_int &x,const large_int &y);
    friend bool operator<(const large_int &x,const large_int &y);
    basic_large_int p;
    bool positive;

    public:
    large_int();
    large_int(const int &x);
    large_int(const basic_large_int &p0,const bool &pos0);

    large_int(string s);
    string str() const;
    int operator[](const int x) const;
    int len() const;
    large_int operator+=(const large_int &y);
    large_int operator-=(const large_int &y);
    large_int operator*=(const large_int &y);
    large_int operator/=(const large_int &y);
    large_int operator%=(const large_int &y);
};

ostream& operator<<(ostream &,const large_int &);
istream& operator>>(istream &,const large_int &);
large_int operator+(const large_int &,const large_int &);
large_int operator-(const large_int &,const large_int &);
large_int operator*(const large_int &,const large_int &);
large_int operator/(const large_int &,const large_int &);
large_int operator%(const large_int &,const large_int &);//not implemented
bool operator==(const large_int &,const large_int &);
bool operator!=(const large_int &,const large_int &);
bool operator<(const large_int &,const large_int &);
bool operator>(const large_int &,const large_int &);
bool operator<=(const large_int &,const large_int &);
bool operator>=(const large_int &,const large_int &);

large_int::large_int():p(0),positive(1) { }
large_int::large_int(const int &x):p(abs(x)),positive(x>=0) { }
large_int::large_int(const basic_large_int &p0,const bool &pos0):p(p0),positive(pos0) { }

int large_int::operator[](const int x) const { return p.a[x]; }
int large_int::len() const { return p.len(); }

large_int::large_int(string s)
{
    positive = 1;
    if (s=="")
        return ;
    positive = 1;
    if (s[0]=='-'){
        p = basic_large_int(s.substr(1,s.size() - 1));
        positive = 0;
    }
    else if (s[0]=='+')
        p = basic_large_int(s.substr(1,s.size() - 1));
    else
        p = basic_large_int(s);
}

string large_int::str() const
{
    string ret = "";
    if (!positive && !(this->p == 0))
        ret = "-";
    ret += p.str();
    return ret;
}

ostream& operator<<(ostream& os,const large_int &x)
{
    os << x.str();
    return os;
}

istream& operator>>(istream& is,large_int &x)
{
    string tmp;
    is >> tmp;
    x = large_int(tmp);
    return is;
}

large_int operator+(const large_int &x,const large_int &y)
{
    if (x.positive==y.positive)
        return large_int((x.p) + (y.p),x.positive);
    if ((x.p)>(y.p))
        return large_int((x.p) - (y.p),x.positive);
    else
        return large_int((y.p) - (x.p),y.positive);
}

large_int operator-(const large_int &x,const large_int &y) { return x + large_int((y.p),!y.positive); }
large_int operator*(const large_int &x,const large_int &y) { return large_int((x.p)*(y.p),!(x.positive ^ y.positive)); }
large_int operator/(const large_int &x,const large_int &y) { return large_int((x.p)/(y.p),!(x.positive ^ y.positive)); }
large_int operator%(const large_int &x,const large_int &y) { return large_int(x.p%y.p,!(x.positive ^ y.positive)); }

large_int large_int::operator+=(const large_int &y) { return (*this)=(*this)+y; }
large_int large_int::operator-=(const large_int &y) { return (*this)=(*this)-y; }
large_int large_int::operator*=(const large_int &y) { return (*this)=(*this)*y; }
large_int large_int::operator/=(const large_int &y) { return (*this)=(*this)/y; }
large_int large_int::operator%=(const large_int &y) { return (*this)=(*this)%y; }

bool operator==(const large_int &x,const large_int &y) { return (x.positive==y.positive) && (x.p==y.p); }
bool operator!=(const large_int &x,const large_int &y) { return !(x==y); }

bool operator>(const large_int &x,const large_int &y)
{
    if (x.positive!=y.positive) return x.positive>y.positive;
    if (x.positive)
        return x.p>y.p;
    else
        return x.p<y.p;
}

bool operator<(const large_int &x,const large_int &y)
{
    if (x.positive!=y.positive) return x.positive<y.positive;
    if (x.positive)
        return x.p<y.p;
    else
        return x.p>y.p;
}

bool operator>=(const large_int &x,const large_int &y) { return !(x<y); }
bool operator<=(const large_int &x,const large_int &y) { return !(x>y); }

void basic_large_int::carry()
{
    for (int i=0;i<len();i++)
        if (a[i]>=ARY){
            if (i==len() - 1)
                a.push_back(0);
            a[i + 1] += a[i]/ARY;
            a[i] %= ARY;
        }
}

basic_large_int::basic_large_int(string s)
{
#ifndef LARGE_ARY_EN
    a.resize(s.size());
    for (int i=0;i<(int)s.size();i++)
        a[i] = s[s.size() - i - 1] - '0';
#else
    int length = (int)ceil(s.size()/4.0);
    a.resize(length);
    fill(a.begin(),a.end(),0);
    for (int i=s.size() - 1;i>=0;i--){
        int ti = i/4;
        int tj = s.size() - i - 1;
        a[ti] = a[ti]*10 + s[tj] - '0';
    }
#endif
}

string basic_large_int::str() const
{
#ifndef LARGE_ARY_EN
    string ret = "";
    int last = len() - 1;
    //    while (last>0 && a[last]==0)
    //        last--;
    for (int i=last;i>=0;i--)
        ret += a[i] + '0';
    return ret;
#else
    string ret = "";
    if (a[len() - 1]/1000) ret += (a[len() - 1]/1000) %10 + '0';
    if (a[len() - 1]/100) ret += (a[len() - 1]/100) %10 + '0';
    if (a[len() - 1]/10) ret += (a[len() - 1]/10) %10 + '0';
    ret += a[len() - 1]%10 + '0';
    for (int i=len() - 2;i>=0;i--){
        ret += (a[i]/1000)%10 + '0';
        ret += (a[i]/100)%10 + '0';
        ret += (a[i]/10)%10 + '0';
        ret += (a[i]/1)%10 + '0';
    }
    return ret;
#endif
}

basic_large_int basic_large_int::operator=(const int &x)
{
    a.resize(1);
    a[0] = x;
    carry();
    return *this;
}

istream& operator>>(istream &is,basic_large_int &x)
{
    string tmp;
    is >> tmp;
    x = basic_large_int(tmp);
    return is;
}

ostream& operator<<(ostream &os,const basic_large_int &x)
{
    os << x.str();
    return os;
}

bool operator==(const basic_large_int &x,const basic_large_int &y)
{
    int xlen = x.len();
    if (xlen!=y.len()) return 0;
    for (int i=0;i<xlen;i++)
        if (x.a[i]!=y.a[i])
            return 0;
    return 1;
}

bool operator<(const basic_large_int &x,const basic_large_int &y)
{
    int xlen = x.len();
    if (xlen!=y.len()) return xlen<y.len();
    for (int i=xlen - 1;i>=0;i--)
        if (x.a[i]!=y.a[i])
            return x.a[i]<y.a[i];
    return 0;
}

bool operator>(const basic_large_int &x,const basic_large_int &y)
{
    int xlen = x.len();
    if (xlen!=y.len()) return xlen>y.len();
    for (int i=xlen - 1;i>=0;i--)
        if (x.a[i]!=y.a[i])
            return x.a[i]>y.a[i];
    return 0;
}

basic_large_int basic_large_int::operator+=(const basic_large_int &y)
{
    if (len()<y.len())
        a.resize(y.len());
    for (int i=0;i<y.len();i++)
        a[i] += y.a[i];
    carry();
    return *this;
}

basic_large_int basic_large_int::operator-=(const basic_large_int &y)
{
    for (int i=0;i<len();i++){
        int cur = 0;
        if (i<y.len())
            cur = y.a[i];
        a[i] -= cur;
        if (a[i]<0)
            a[i] += ARY,a[i + 1] --;
    }
    minimize_length();
    return *this;
}

basic_large_int operator*(const basic_large_int &x,const basic_large_int &y)
{
    basic_large_int ans;
    int xlen = x.len(),ylen = y.len();
    ans = 0;
    ans.a.resize(xlen + ylen);
#ifndef LARGE_ARY_EN
    for (int i=0;i<xlen;i++)
        for (int j=0;j<ylen;j++)
            ans.a[i + j] += x.a[i] * y.a[j];
#else
    for (int i=0;i<xlen;i++)
        for (int j=0;j<ylen;j++){
            ans.a[i + j] += x.a[i] * y.a[j];
            if (ans.a[i + j]>ARY){
                ans.a[i + j + 1] += ans.a[i + j]/ARY;
                ans.a[i + j] %= ARY;
            }
        }
#endif
    ans.carry();
    ans.minimize_length();
    return ans;
}

basic_large_int operator/(basic_large_int x,const basic_large_int &y)
{
    basic_large_int ans;
    int xlen = x.len(),ylen = y.len();
    int tmp = xlen - ylen + 1;
    int len = max(tmp,1);
    ans.a.resize(len);
    fill(&ans.a[0],&ans.a[len],0);
    for (int i=tmp - 1;i>=0;i--){
        if (i<tmp - 1)
            x.a[i + ylen - 1] += x.a[i + ylen]*ARY;
        while (1){
            bool flag = 0;
            for (int j=ylen - 1;j>=0;j--)
                if (x.a[i + j]!=y.a[j]){
                    flag = x.a[i + j]<y.a[j];
                    break;
                }
            if (flag)
                break;
            ans.a[i] ++;
            for (int j=0;j<ylen;j++){
                x.a[i + j] -= y.a[j];
                if (x.a[i + j]<0){
                    assert(i + j + 1<xlen);
                    x.a[i + j + 1] --;
                    x.a[i + j] += ARY;
                }
            }
        }
    }
    ans.carry();
    ans.minimize_length();
    return ans;
}

basic_large_int operator%(basic_large_int x,const basic_large_int &y)
{
    int xlen = x.len(),ylen = y.len();
    int tmp = xlen - ylen + 1;
    //int len = max(tmp,1);
    for (int i=tmp - 1;i>=0;i--){
        if (i<tmp - 1){
            x.a[i + ylen - 1] += x.a[i + ylen]*10;
            x.a[i + ylen] = 0;
        }
        while (1){
            bool flag = 0;
            for (int j=ylen - 1;j>=0;j--)
                if (x.a[i + j]!=y.a[j]){
                    flag = x.a[i + j]<y.a[j];
                    break;
                }
            if (flag)
                break;
            for (int j=0;j<ylen;j++){
                x.a[i + j] -= y.a[j];
                if (x.a[i + j]<0){
                    assert(i + j + 1<xlen);
                    x.a[i + j + 1] --;
                    x.a[i + j] += ARY;
                }
            }
        }
    }
    x.minimize_length();
    return x;
}
